package algorithms.heap;

import algorithms.Util;

/**
 * 使用数组实现的隐式二叉树，将完全二叉树映射到数组中存储,然后从数组生成堆
 * 
 * @author syx
 *
 */
public class Heapify {
	private int popCount;

	// 数组 索引从0开始,0的子节点为1,2,1的子节点是3,4,所以子节点的index是2i+1和2i+2
	int left(int index) {
		return 2 * index + 1;
	}

	int right(int index) {
		return 2 * index + 2;
	}

	/**
	 * 从数组指定索引开始构造最大堆（该数字是完全二叉树的压缩映射）。
	 * 
	 * 在使用此算法来构建一个最大堆时，需要自底向上来检查和构建堆。
	 * 
	 * 算法接受1个数组A和1个索引i，A[i]的两个节点都不应比它大。 <br>
	 * 否则， 选出最大的元素保存在A[i]，并将较小的元素交换到子树， <br>
	 * 然后算法自顶向下检查并修复堆的性质直到叶子节点或者没有发现任何违反堆性质的情况。 <br>
	 * Heapify的时间复杂度为O(lg
	 * n)，其中n是元素的总数。这是因为算法中的循环次数和完全二叉树的高度成正比
	 * 
	 * @param a
	 * @param index
	 * @param length
	 */
	void heapify(Integer[] a, int index, int length) {
		int max = index;
		while (true) {
			System.out.println("index:" + index);
			int l = left(index);
			int r = right(index);
			if (l < length && a[l] > a[max]) {
				max = l;
			}
			if (r < length && a[r] > a[max]) {
				max = r;
			}
			if (max != index) {
				Util.exchange(a, index, max);
				index = max;
			} else {
				break;
			}
		}

	}

	/**
	 * 对于一个完全二叉树，初最后一层外，第i层的节点数 ni= 2^(i-1)
	 * ,当其是完美二叉树时（也即最后一层也是满的），最后一层节点数为
	 * 2^(h-1),h为树的高度，那么树的总节点数为：2^0+2^1+...+2^(h-1)=2^h - 1,
	 * 
	 * 最后一层的节点都是叶子节点，肯定满足最大堆（小）的性质，所以无需检查，
	 * 所以可以从倒数第二层开始往上检查，也就是从2^h-1-2^(h-1)的节点开始，显然是在n/2之前的索引，
	 * （n为数组长度也即总节点数）
	 * 
	 * @param a
	 */
	public void buildHeapFromArray(Integer[] a) {
		int len = a.length;
		for (int i = len >> 1; i >= 0; i--) {
			heapify(a, i, len);
		}
	}

	public int pop(Integer[] a) {
		popCount++;
		Util.exchange(a, 0, a.length - popCount);
		// 最后popCount个元素放弃
		heapify(a, 0, a.length - popCount);
		int result = a[a.length - popCount];
		return result;
	}

	public static void main(String[] args) {
		Heapify h = new Heapify();

		Integer[] a = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
		for (int i = 1; i < a.length; i++) {
			h.heapify(a, i, a.length);
		}
		Util.print(a);
		System.out.println("---");
		Integer[] ac = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
		h.buildHeapFromArray(ac);
		Util.print(ac);
		// System.out.println(h.pop(ac));
		Util.print(ac);
		// 连续pop，有序结果集
		for (int i = 0; i < ac.length; i++) {
			System.out.println(h.pop(ac));
		}
	}
}
